#include <iostream>
using namespace std;

void printArr(int arr[])
{
    for (int i = 0; arr[i]; i++)
    {
        printf("%d ", arr[i]);
    }
    puts("");
}

void swap(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

void shell(int arr[], int n)
{
    int d, i, j;
    for (d = n / 2; d >= 1; d >>= 1)
    {
        for (i = 0; i < d; i++)
        {
            for (j = i + d; j < n; j += d)
            {
                if (arr[j] < arr[j - d])
                {
                    int k = j - d;
                    int temp = arr[j];
                    while (k >= 0 && arr[k] > temp)
                    {
                        arr[k + d] = arr[k];
                        k -= d;
                    }
                    arr[k + d] = temp;
                }
            }
        }
    }
}

int arr[12] = {2, 1, 5, 7, 1, 4, 6, 2, 7, 2, 67, 32};
int main(int argc, char const *argv[])
{
    int n = sizeof(arr) / sizeof(arr[0]);
    printArr(arr);
    shell(arr, n);
    printArr(arr);
    return 0;
}
